// 教科书中的朴素哈希表实现
// 实现的底层是一个数组，数组内的元素是链表单节点，
// 本质上是HashSet的实现

import { Node } from "../3、链表与变相链表的实现/链表"
import { HashSetContent } from './type';

export class HashSet<T = unknown> {
    protected size: number;
    protected hashSet: HashSetContent<T>[];// 哈希集合内容
    // 构造函数
    constructor(size: number) {
        this.hashSet = new Array(size).fill(null);
        this.size = 0;
    }
    // 计算哈希值
    protected getHashCode(value: T): number {
        let hashStr = '';// 哈希字符
        // 判断是不是复杂数据类型
        if (value instanceof Object) {
            hashStr = Object.prototype.toString.call(value);
        } else {
            hashStr = String(value);
        }
        return hashStr.charCodeAt(0) % this.hashSet.length;
    }
    // 存储方法
    set(value: T): boolean {
        const hashCode = this.getHashCode(value);
        let currValue = this.hashSet[hashCode];
        if (currValue === null) {// 不存在冲突时，直接插入新节点
            this.hashSet[hashCode] = new Node(value);
        } else {// 存在冲突，同时需要判断是否出现过重复值
            // 边界情况，先判断当前节点是否重复
            if (currValue.val === value) {
                return false;
            }
            while (currValue.next !== null) {
                if (currValue.next.val === value) {
                    return false;
                }
                currValue = currValue.next;
            }
            // 生成新节点
            currValue.next = new Node(value);
        }
        this.size++;
        return true;
    }

    // 判断集合中是否存在该值
    has(value: T): boolean {
        const hashCode = this.getHashCode(value);
        let currValue = this.hashSet[hashCode];
        while (currValue !== null) {
            if (currValue.val === value) {
                return true;
            }
            currValue = currValue.next;
        }
        return false;
    }

    // 删除方法
    delete(value: T): boolean {
        const hashCode = this.getHashCode(value);
        let currValue = this.hashSet[hashCode];
        // 边界情况，对应位置只有一个节点
        if (currValue?.val === value) {
            this.hashSet[hashCode] = null;
            this.size--;
            return true;
        }
        // 以头节点为首开始查找
        while (currValue?.next) {
            if (currValue.next.val === value) {
                currValue.next = currValue.next.next;
                this.size--;
                return true;
            }
        }
        return false;
    }

    // 返回哈希集合长度
    length(): number {
        return this.size;
    }

    // 展示输出方法
    show(): void {
        const exists: T[] = [];
        for (let i = 0; i < this.hashSet.length; i++) {
            let currValue = this.hashSet[i];
            while (currValue !== null) {
                exists.push(currValue.val);
                currValue = currValue.next;
            }
        }
        console.log(...exists);// 控制台输出
    }
}


// 测试用例
const hs1 = new HashSet(10)
console.log(hs1.set('1'))
console.log(hs1.set('aa'))
console.log(hs1.set('6a'))
console.log(hs1.set('75'))
console.log(hs1.set('aa'));// false
console.log(hs1.set(1));
console.log(hs1.set(1));// false
console.log(hs1.has(1));
console.log(hs1.set(false));
console.log(hs1.set(true));
console.log(hs1.has(true));
console.log(hs1.set(12));
console.log(hs1.set({ a: 1, b: 2 }));
console.log('size:' + hs1.length());// 9
hs1.show();